package leetcode_800;

import java.util.PriorityQueue;

/**
 *@author 周杨
 *SwimInRisingWater_778_ 一个人从[0,0]企图游到[N-1,N-1] 这个人每次只能到达比自己当前高度低的位置 每秒会增加当前高度 问最短时间
 *describe:迪杰斯特拉的典型实现方式 建立优先队列连接周围联通节点 每次选择最短的距离到达  AC 61%
 *2018年10月20日 上午11:05:18
 */
public class SwimInRisingWater_778_ {
	class Node {
		  int row;
		  int col;
		  int dist;
		  Node(int row, int col, int dist) {
		    this.row = row;
		    this.col = col;
		    this.dist = dist;
		  }
	}
	 private static int[][] DIRECTIONS = {{0,1}, {0,-1}, {1,0}, {-1,0}};

	public int swimInWater(int[][] grid) {
		int n = grid.length;
		boolean[][] visited = new boolean[n][n];// 不允许重复达到某个点
		PriorityQueue<Node> pq = new PriorityQueue<Node>((n1, n2) -> n1.dist - n2.dist);
		pq.add(new Node(0, 0, grid[0][0]));
		visited[0][0] = true;
		while (!pq.isEmpty()) {
			Node current = pq.poll();
			for (int i = 0; i < 4; i++) {// 试图在当前点走向四个地点 因为当前点是绝对能达到的点 否则不会加入优先队列
				int nr = current.row + DIRECTIONS[i][0];
				int nc = current.col + DIRECTIONS[i][1];
				if (nr < 0 || nc < 0 || nr >= n || nc >= n || visited[nr][nc])
					continue;
				int distToNode = Math.max(current.dist, grid[nr][nc]);// 当前点的高度和能否走到该点
				pq.add(new Node(nr, nc, distToNode));// 建立联通向量 只要高度到达 一定能达到
				visited[nr][nc] = true;
				if (nr == n - 1 && nc == n - 1)
					return distToNode;
			}
		}
		return 0;
	}
	

}
